package LeetCode刷题.之前的算法;

import java.util.Scanner;

//斜蛇形矩阵
public class SnackTriangle {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            if(n==3){
                n--;
            }
            int map[][] = new int[n][n];
            if (n % 2 != 0) {
                //是奇数
                snack1(map, n);
            } else {
                snack2(map, n);
            }
            print(map,n);
        }
    }

    private static void snack1(int map[][], int n) {//n为奇数
        int tot = n * (n + 1) / 2;
        map[0][0] = 1;
        map[1][0] = 2;
        map[0][1] = 3;
        int i,j;
        if(n>3) {
            map[0][2] = 4;
            i = 0;
            j = 2;
            int num = 4;
            int len1 = 2;//每一层元素的个数
            int len2 = 2;
            while (num < tot) {
                while (len1 != 0 && i + 1 < n && j - 1 >= 0&&num<tot) {
                    map[++i][--j] = ++num;
                    len1--;
                }//向左下方走
                if(i+1<n&&num<tot) {
                    map[++i][j] = ++num;//到了左边界，再向下走一个
                }
                len2++;
                len1 = len2;
                while (len1 != 0 && i - 1 >= 0 && j + 1 < n&&num<tot) {
                    map[--i][++j] = ++num;
                    len1--;
                }//向右上方走
                if(j+1<n&&num<tot) {
                    map[i][++j] = ++num;//到了右边界，再向右走一个
                }
                len2++;
                len1 = len2;
            }
        }
    }

    private static void snack2(int map[][], int n) {
        int tot = n * (n + 1) / 2;
        map[0][0] = 1;
        map[0][1] = 2;
        map[1][0] = 3;
        int i,j;
        if(n>2) {
            map[2][0] = 4;
            i = 2;
            j = 0;
            int num = 4;
            int len1 = 2;//每一层元素的个数
            int len2 = 2;
            while (num < tot) {
                while (len1 != 0 && i - 1 >= 0 && j + 1 < n&&num<tot) {
                    map[--i][++j] = ++num;
                    len1--;
                }//向右上方走
                if(j+1<n&&num<tot) {
                    map[i][++j] = ++num;//到了右边界，再向右走一个
                }
                len2++;
                len1 = len2;

                while (len1 != 0 && i + 1 < n && j - 1 >= 0&&num<tot) {
                    map[++i][--j] = ++num;
                    len1--;
                }//向左下方走
                if(i+1<n&&num<tot) {
                    map[++i][j] = ++num;//到了左边界，再向下走一个
                }
                len2++;
                len1 = len2;
            }
        }
    }
    public static void print(int map[][],int n){
        for(int i=0;i<n;i++){
            for(int j=0;j<n-1;j++){
                if(map[i][j]!=0){
                    System.out.printf("%5d",map[i][j]);
                }
            }
            if(map[i][n-1]!=0) {
                System.out.printf("%5d\n",map[i][n - 1]);
            }
            else{
                System.out.println();
            }
        }
    }
}
